package 高效制胜._04;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/10 9:39
 * 分割等和子集
 * 算法：动态规划
 * 01 背包问题
 */
public class _416 {
    public static void main(String[] args) {
        for (int i = 1; i >= 2; i++) System.out.println(1);
    }

    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        if (sum % 2 != 0) return false;
        sum = sum >> 1;
        int[] dp = new int[sum + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = sum; j >= nums[i]; j--)
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
        }
        return dp[sum] == sum;
    }

}
